1. Field of the Invention
The present invention relates to a processor circuit capable of sorting a train of data in a prescribed order at high speed, and more specifically to a sort processor circuit capable of generating heap data and sorting the train of data by heapsort at high speed.
2. Description of the Related Art
"Sorting" is an operation of arranging an arbitrary number of data in ascending order or descending order. Sorting is one of the basic operations in a computer system, and widely used in various applications. Therefore, if sorting can be performed at high speed, it is expected that application programs and jobs executed on computers can be performed at higher speed.
Studies for increasing speed in sorting have been made, starting almost simultaneously with the birth of computers. Various and many efforts have been made in this field, including proposals of hardware sort algorithms and trial of sort processors (integrated circuit devices for performing sorting exclusively). However, there is only a few hardware sort processors practically available at present which can process a large amount of data at high speed.
Though there are a number of algorithms for sorting, sort processors commercially available at present all utilize a so-called mergesort algorithm.
A method of sorting called heapsort has been known as opposed to mergesort. Heapsort is a method of sorting utilizing "heap data".
The heap is typically a data structure called a sorted labelled binary tree. One example is shown in FIG. 1.
The "binary tree" is defined as one satisfying the following conditions.
(a) A binary tree has a specific one node which is distinguished from other nodes, as shown by the node N1) of FIG. 1. This specific node is referred to as a root.
(b) Nodes other than the root can be divided into sets of nodes which do not have common portions. In the example shown in FIG. 1, the nodes can be divided into a set of nodes below the node N2), and a set of nodes below the node N3). A set of nodes satisfying the conditions (a) and (b) is referred to as a "tree".
(c) Every node has at most two subtrees. At this time, the node itself is called parent, and the node at the top of a subtree is called a child.
Brief definition of the binary tree is as given above. The binary tree realizes data structures having different meanings by defining relation of data between the parent and child at a branch.
"Heap" refers to a binary tree in which a prescribed relation holds between magnitudes of data of any parent and child. FIG. 1 shows one such example in which every parent has data of larger value than its child (children). In the example of FIG. 1, there is such a rule that parent's data has larger value than the child's data. Therefore, as can be understood from the example shown in FIG. 1, in heap data, the data at the root has the maximum (or minimum) value. However, there is no definite order between the two children branching from a parent.
One-dimensional array representation is one example of a data structure representing heap data. In the one-dimensional array representation, the parent-child relationship of the binary tree is obtained by address calculation. When heap data are to be stored in one-dimensional array, the following rule is applied. In the following description, it is assumed that there are n data to be stored, and the data are stored in a[1] to a[n] of a one dimensional array having n elements. The data corresponding to the root is simply referred to as "root", and similarly, data corresponding to parent and child are respectively referred to as "parent" and "child".
(1) In a[1], the root is stored.
(2) Children of a[i] are a[2i] and a[2i+1].
(3) Parent of a[i] (where i.noteq.1) is a[i/2] (when i is an even number), or a [(i-1)/2] (when i is an odd number). In the following description, the parent of a [i] will be represented as a[i/2], no matter whether i is an even number or odd number.
When the heap data shown in FIG. 1 is stored in the one dimensional array in accordance with the rule mentioned above, data stored in one dimensional array such as shown in FIG. 2 results. As can be readily seen from the comparison between FIGS. 2 and 1, the data of the root is stored in a[1], the data of a child N2) is stored in a[2] and data of a child N3) is stored in a[3], and in this manner, children data are respectively stored in array elements determined in accordance with the above described rule.
A method of generating heap data will be described. It is assumed that n data are stored in an array a[1] to a[n], and there is no rule in the order of storing the data. The data will be made heap through the following processes.
(S1) A first node having a child (children) is found, going upward starting from the lowermost node of the binary tree. Assuming that every parent has two children, the node thus found corresponds to a[n/2].
(S2) A subtree below and including that node which was found in step S1 is made heap. More specifically, the following process is performed. In the following example, generation of heap data in which a parent has larger data than its child (children) is intended.
(Sa) A node of interest (parent) is compared with its children. If the parent is larger, the flow proceeds to step S3. If at least one of the children is larger, the larger one of the children and the parent are exchanged.
(Sb) The same process as the above described step Sa is repeated, starting from the position to which the node of interest has been transferred (the position is now the new node of interest), until the node of interest comes to be larger than any child, or until there is no child left.
(S3) The step S2 is repeated on every node going back from the node found in step S1, until the root is reached.
If heap data satisfying the condition that the parent is smaller than its children is to be generated, the relation of magnitudes between the parent and the child should be reversed.
A heapsort algorithm will be described. The heapsort algorithm is for sorting data in an ascending order or a descending order, utilizing the data which is made heap. Heapsort is performed in accordance with the following procedure. In the following, an example is discussed in which data is sorted in an ascending order, utilizing heap data in which parent is larger than its children.
(S1) Heap data is prepared as shown in FIG. 3. In the root of the heap data, the largest data is stored.
(S2) The root data and the last one of the heap data are exchanged. The state of this binary tree after this exchange is as shown in FIG. 4.
(S3) Data of the binary tree except the last data (in FIG. 5, "21") are arranged to be made heap. At this time, respective nodes of subtrees except the root are already made heap. Therefore, the new binary tree can be re-sorted to be heaped, simply by performing the step S2 of the process for generating heap data described above.
For example, in the binary tree shown in FIG. 4, at first the root and its child "16" are exchanged (FIG. 5). Then, the former root "4" which has been exchanged, and its child "13" are exchanged (FIG. 6). As is apparent from FIG. 6, the binary tree except the last data "21" is already heap. At this time, the second largest one of the original n data is stored in the root.
(S4) Steps S2 and S3 are repeated. Here, it is assumed that in step S2, the root of the binary tree which has been sorted into heap data in the immediately preceding step S3 is exchanged for the last data of the binary tree. Accordingly, the number of data of the binary tree which is re-sorted to provide heap data in step S3 decreases one by one.
For example, when the root "16" of the binary tree shown in FIG. 6 is exchanged for the last data "1" of the re-sorted binary tree, a binary tree shown in FIG. 7 results. By performing the step S2 of the process for generating heap data starting from the root "1" as described above, a binary tree shown in FIG. 8 is obtained. At this time, a third largest data of the original n data is stored in the root. Further, the root "13" shown in FIG. 8 is exchanged for the last data "8" of the re-sorted binary tree, and the step S2 of the process for generating heap data mentioned above is performed, focusing on the root.
Such processes are repeated thereafter. In that case, the number of data of the re-sorted binary tree decreases one by one as mentioned above. After resorting, largest data among the re-sorted data is stored in the root. Since this root is exchanged for the last data of the sorted binary tree, largest to smallest data are stored in order from the last node to the root of the binary tree.
When the process of step S4 is completed, such data as shown in FIG. 9 is obtained. The data shown in FIG. 9 is stored in such a one dimensional array as shown in FIG. 2, in accordance with the relation shown in FIGS. 1 and 2. It can be seen that finally, data are stored in an ascending order in this array. More specifically, by heapsort, n data are arranged in the ascending order, the result of which is stored in the one-dimensional array.
The heapsort algorithm described above has been conventionally known, and processed by means of a software, since it can be implemented by a prescribed procedure.
When the above described heapsort algorithm is to be implemented by a software, a number of data comparison and rewriting including nesting must be performed for one sorting, which hinders high speed operation. In a system utilizing a database, it is necessary to perform such sorting for a number of times, and therefore the overall processing time will be longer. In such a system, the amount of data to be processed is also large, and therefore overall sorting process requires considerably long time. Further, generation of heap data itself should preferably be performed at high speed.